package DFA

import (
	"strings"
)

// CreateNFA 从后缀表达式创建NFA
func CreateNFA(postfix string) NFA {
	var ns = CreateStack() //保存节点的栈
	var nameId = 0         //命名序号
	for i := 0; i < len(postfix); i++ {
		switch postfix[i] {
		case '^':
			a := ns.Pop()
			b := ns.Pop()
			ns.Push(createAndNode(b, a, &nameId))
		case '*':
			ns.Pop()
			b := ns.Pop()
			ns.Push(createMulNode(b, &nameId))
		case '|':
			a := ns.Pop()
			b := ns.Pop()
			ns.Push(createOrNode(b, a, &nameId))
		default:
			ns.Push(createSingleNode(postfix[i], &nameId))
		}
	}
	var res = ns.Pop()
	return res
}

// CreatePostfix 创建后缀表达式
func CreatePostfix(s string) string {
	// 运算符权重
	var power = map[byte]int{
		'*': 3,
		'^': 2,
		'|': 1,
	}
	var sb = strings.Builder{}
	var fs = CreateFlagStack() //符号栈
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			fs.Push('(')
		} else if s[i] == ')' {
			//符号出栈直到遇到‘(’ ，‘（’出栈但不写入结果
			for f := fs.Pop(); f != '('; f = fs.Pop() {
				sb.WriteByte(f)
			}
		} else if s[i] == '*' || s[i] == '|' || s[i] == '^' {
			//当为运算符时，将栈中优先级大于等于当前运算符的出栈写入结果，最后将当前运算符入栈
			p := power[s[i]]
			for !fs.IsEmpty() {
				f := fs.Peek()
				if f == '(' {
					break
				}
				if power[f] >= p {
					fs.Pop()
					sb.WriteByte(f)
				} else {
					break
				}
			}
			fs.Push(s[i])
		} else {
			//遇到其他符号直接写入结果
			sb.WriteByte(s[i])
		}
	}
	for !fs.IsEmpty() {
		sb.WriteByte(fs.Pop())
	}
	return sb.String()
}

// PrevTreat 字符串预处理 插入^ 和空格占位符
func PrevTreat(s string) string {
	var sb = strings.Builder{}
	//在*后插入空格，将其转为二元运算符
	for i := 0; i < len(s); i++ {
		sb.WriteByte(s[i])
		if s[i] == '*' {
			sb.WriteByte(' ')
		}
	}

	s = sb.String()
	sb.Reset()
	for i := 0; i < len(s)-1; i++ {
		sb.WriteByte(s[i])
		//处理 a^a 或 a^(
		if s[i] != '(' && s[i] != ')' && s[i] != '|' && s[i] != '*' && s[i+1] != ')' && s[i+1] != '|' && s[i+1] != '*' {
			sb.WriteByte('^')
		}
		//处理 )^( 或 )^a
		if s[i] == ')' && s[i+1] != '|' && s[i+1] != '*' {
			sb.WriteByte('^')
		}
	}
	sb.WriteByte(s[len(s)-1])
	return sb.String()
}
